{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #计算二叉树的深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: calculateDepth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #计算二叉树的深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某公司架构以二叉树形式记录，请返回该公司的层级数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1695101942-FSrxqu-image.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1, 2, 2, 3, null, null, 5, 4, null, null, 4]\n",
    "<strong>输出: </strong>4\n",
    "<strong>解释: </strong>上面示例中的二叉树的最大深度是 4，沿着路径 1 -&gt; 2 -&gt; 3 -&gt; 4 或 1 -&gt; 2 -&gt; 5 -&gt; 4 到达叶节点的最长路径上有 4 个节点。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>节点总数 &lt;= 10000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 104&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/\">https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-cha-shu-de-shen-du-lcof](https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-cha-shu-de-shen-du-lcof](https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2,3,null,null,5,4,null,null,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        q = deque([root])\n",
    "        res = []\n",
    "        while q:\n",
    "            temp = []\n",
    "            for i in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                temp.append(node.val)\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "                \n",
    "            res.append(temp)\n",
    "        \n",
    "        return len(res)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        stk = [root]\n",
    "        res = []\n",
    "        while stk:\n",
    "            tmp = []\n",
    "            for _ in range(len(stk)):\n",
    "                i = stk.pop(0)\n",
    "                tmp.append(i.val)\n",
    "                if i.left:\n",
    "                    stk.append(i.left)\n",
    "                if i.right:\n",
    "                    stk.append(i.right)\n",
    "            res.append(tmp)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue=[root]\n",
    "        res=0\n",
    "        while queue:\n",
    "            tmp=[]\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            queue=tmp\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        res = 0\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                if node.left: que.append(node.left)\n",
    "                if node.right: que.append(node.right)\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue = [root]\n",
    "        res = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop()\n",
    "                if node.left:tmp.append(node.left)\n",
    "                if node.right:tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue, res = [root], 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    tmp.append(node.left)\n",
    "                if node.right:\n",
    "                    tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        '''\n",
    "        def func1(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            left = func1(root.left)\n",
    "            right = func1(root.right)\n",
    "            return max(left,right)+1\n",
    "        \n",
    "        return func1(root)\n",
    "        '''\n",
    "        queue = [root]\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return 0\n",
    "        while queue:\n",
    "            temp = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    temp.append(node.left)\n",
    "                if node.right:\n",
    "                    temp.append(node.right)\n",
    "            queue = temp\n",
    "            res += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue, res = collections.deque(), 0\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue, res = [root], 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        myque = queue.Queue()\n",
    "        myque.put_nowait(root)\n",
    "        depth = 0\n",
    "        while not myque.empty():\n",
    "            for _ in range(myque.qsize()):\n",
    "                node = myque.get_nowait()\n",
    "                if node.left:\n",
    "                    myque.put_nowait(node.left)\n",
    "                if node.right:\n",
    "                    myque.put_nowait(node.right)\n",
    "            depth += 1\n",
    "        return depth\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        que = collections.deque()\n",
    "        que.append(root)\n",
    "        res = 0\n",
    "        while que:\n",
    "            for i in range(len(que)):\n",
    "                node = que.popleft()\n",
    "                if node.left: que.append(node.left)\n",
    "                if node.right: que.append(node.right)\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        n = 0\n",
    "        while queue:\n",
    "            n += 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left: queue.append(node.left)\n",
    "                if node.right: queue.append(node.right)\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        if not root:\n",
    "            return ans\n",
    "        q = Queue(0)\n",
    "        q.put(root)\n",
    "\n",
    "        while not q.empty():\n",
    "            n = q.qsize()\n",
    "            for _ in range(n):\n",
    "                node = q.get()\n",
    "                if node.left:\n",
    "                    q.put(node.left)\n",
    "                if node.right:\n",
    "                    q.put(node.right)\n",
    "\n",
    "            ans += 1\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        res = 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.pop()\n",
    "                if node.left:tmp.append(node.left)\n",
    "                if node.right:tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        queue, res = [root], 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        q=collections.deque()\n",
    "        q.append(root)\n",
    "        res=0\n",
    "        while len(q)>0:\n",
    "            layer_num=len(q)\n",
    "            res+=1\n",
    "            for _ in range(layer_num):\n",
    "                node=q.popleft()\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        q = [root]\n",
    "        depth = 0\n",
    "        while q:\n",
    "            tmp_q = []\n",
    "            while q:\n",
    "                node = q.pop(0)\n",
    "                if node.left is not None:\n",
    "                    tmp_q.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    tmp_q.append(node.right)\n",
    "            depth += 1\n",
    "            q = tmp_q\n",
    "        return depth\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:    return 0\n",
    "        queue, depth = [root], 0\n",
    "\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            depth += 1\n",
    "            queue = tmp\n",
    "        return depth\n",
    "\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        # 空节点直接返回\n",
    "        if not root:    return 0\n",
    "        # 初始化队列，并添加根节点\n",
    "        queue, depth = Queue(), 0\n",
    "        queue.put_nowait(root)\n",
    "\n",
    "        # 遍历二叉树\n",
    "        while not queue.empty():\n",
    "            # 注意：虽然queue是不断变化的，但是整个过程中只执行一次len(queue.qsize())\n",
    "            # 因此range(queue.qsize())的大小不会发生改变\n",
    "            for _ in range(queue.qsize()):\n",
    "                node = queue.get_nowait()\n",
    "                if node.left: queue.put_nowait(node.left)\n",
    "                if node.right: queue.put_nowait(node.right)\n",
    "            depth += 1\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        queue, res = [root], 0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        if not root:\n",
    "            return res\n",
    "        que=[root]\n",
    "        while que:\n",
    "            tmp=[]\n",
    "            for node in que:\n",
    "                if node.left:tmp.append(node.left)\n",
    "                if node.right:tmp.append(node.right)\n",
    "            que=tmp\n",
    "            res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        # way1\n",
    "        # return max(self.calculateDepth(root.left),self.calculateDepth(root.right))+1\n",
    "        # way2\n",
    "        queue,res = [root],0\n",
    "        while queue:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right:tmp.append(node.right)\n",
    "            queue = tmp\n",
    "            res+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:return 0\n",
    "        deque,res = collections.deque(),0\n",
    "        deque.append(root)\n",
    "        while deque:\n",
    "            res += 1\n",
    "            for i in range(len(deque)):\n",
    "                node = deque.popleft()\n",
    "                if node.left:deque.append(node.left)\n",
    "                if node.right:deque.append(node.right)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0\n",
    "        queue, res = [root], 0\n",
    "        while queue != []:\n",
    "            tmp = []\n",
    "            for node in queue:\n",
    "                if node.left: tmp.append(node.left)\n",
    "                if node.right: tmp.append(node.right)\n",
    "            queue = []\n",
    "            queue.extend(tmp)\n",
    "            res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        myque = deque([root])\n",
    "        depth = 0\n",
    "        while myque:\n",
    "            for _ in range(len(myque)):\n",
    "                node = myque.popleft()\n",
    "                if node.left:\n",
    "                    myque.append(node.left)\n",
    "                if node.right:\n",
    "                    myque.append(node.right)\n",
    "            depth += 1\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfsDepth(root: Optional[TreeNode]) -> int:\n",
    "            if not root:return 0\n",
    "            else: return max(dfsDepth(root.left),dfsDepth(root.right))+1\n",
    "        \n",
    "        if not root:return 0\n",
    "        else:return dfsDepth(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        def max_depth(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            left_max = max_depth(root.left)\n",
    "            right_max = max_depth(root.right)\n",
    "            return max(left_max, right_max) + 1\n",
    "        return max_depth(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self,root,res,count):\n",
    "        if not root:return\n",
    "        count+=1\n",
    "        if not root.left and not root.right:res.append(count)\n",
    "        else:\n",
    "            self.dfs(root.left,res,count)\n",
    "            self.dfs(root.right,res,count)\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res=[]\n",
    "        self.dfs(root,res,0)\n",
    "        if res==[]:return 0\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: TreeNode) -> int:\n",
    "        if not root: return 0\n",
    "        return max(self.calculateDepth(root.left), self.calculateDepth(root.right)) + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root: return 0#没有节点\n",
    "        return max(self.calculateDepth(root.right),self.calculateDepth(root.left))+1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        def recur(node,cnt):\n",
    "            if not node: return\n",
    "            \n",
    "            cnt+=1\n",
    "            nonlocal res\n",
    "            res=max(cnt,res)\n",
    "            recur(node.left,cnt)\n",
    "            recur(node.right,cnt)\n",
    "        recur(root,0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        l=self.calculateDepth(root.left)\n",
    "        r=self.calculateDepth(root.right)\n",
    "        return max(l,r)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root: Optional[TreeNode], step: int) -> int:\n",
    "        if not root: return 0\n",
    "        left_maxi = self.dfs(root.left, step + 1)\n",
    "        right_maxi = self.dfs(root.right, step + 1)\n",
    "        total = left_maxi + right_maxi\n",
    "        return max(left_maxi, right_maxi) + 1\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        if root is None:\n",
    "            return 0\n",
    "        left=self.calculateDepth(root.left)\n",
    "        right=self.calculateDepth(root.right)\n",
    "        return 1+max(left,right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.calculateDepth(root.left)\n",
    "        right = self.calculateDepth(root.right)\n",
    "        return 1+max(left, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def calculateDepth(self, root):\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.calculateDepth(root.left), self.calculateDepth(root.right)) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root : return 0\n",
    "        return max(self.calculateDepth(root.left),self.calculateDepth(root.right)) +1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.calculateDepth(root.left), self.calculateDepth(root.right))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.calculateDepth(root.left),self.calculateDepth(root.right))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.calculateDepth(root.left),self.calculateDepth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        left_de = self.calculateDepth(root.left)\n",
    "        right_de = self.calculateDepth(root.right)\n",
    "        return max(left_de, right_de) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return max(self.calculateDepth(root.left), self.calculateDepth(root.right))+1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def fn(root):\n",
    "            if not root: return 0\n",
    "            return max(fn(root.left), fn(root.right)) + 1\n",
    "        \n",
    "        return fn(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return max(self.calculateDepth(root.left),self.calculateDepth(root.right))+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        left_num = self.calculateDepth(root.left)\n",
    "        right_num = self.calculateDepth(root.right)\n",
    "        return max(left_num, right_num) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def calculateDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            return max(dfs(root.left), dfs(root.right))+1\n",
    "        return dfs(root)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
